package com.mgq.algorithm.bit;

/**
 * 判断一个32位整数,是否是2的幂和4的幂
 */
public class PowerJudge {
    /**
     * 判断一个数是否是4的幂条件
     * 首先需要保证是2的幂
     * 4^0 0000001 偶数项0为1
     * 4^1 0000100 偶数项2为1
     * 4^2 0010000 偶数项4为1
     * 4^3 1000000 偶数项6为1
     *
     * x & 01010101010101010101 ==0 不是4的幂,!=0 是4的幂
     * @param n
     * @return
     */
    public static boolean powerJudge(int n) {
        //16进制,每4位表示一位    0x55555555表示 01010101010101.....
        return (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
    }

    /**
     * 判断一个数是否是2的幂
     * 一个数只能有一个1,就是2的幂
     * 如 01,10,100,1000,10000
     *    1  2  4   8     16
     *    方法一:把这个数的最右侧1找到.看和原来的数是否相等,相等就说明是2的幂
     * @param n
     * @return
     */
    public static boolean judge2Power(int n) {
        return (n & (~n + 1))==n;
    }

    /**
     * 方法2,直接减去1, 就会造成错位,然后进行&运算
     * 01 10 100 1000
     * 00 01 011 0111
     * 取余就是0,说明就是2的幂
     * @param n
     * @return
     */
    public static boolean judge2Power2(int n) {
        return (n & (n - 1))==0;
    }


    public static void main(String[] args) {
        System.out.println(judge2Power(16));
        System.out.println(judge2Power(7));

        System.out.println(judge2Power2(16));
        System.out.println(judge2Power2(7));
    }
}
